package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.TwoProblem;
import cn.pugle.oj.catalog.Unknown;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;

/**
 * https://leetcode.com/problems/find-all-anagrams-in-a-string/
 * <p>
 * see {@link LC76_4}
 * <p>
 * 438 找目标abc, 相当于有三个目标水位, 小valid, 所有都满足是大valid
 * 利用这个思想, 不存在于串p中的字符, 比如e, 其实不用特殊考虑, 就是要求e的水位是0而已, 按照这个
 * 可以写更简化的代码
 *
 * @author tzp
 * @since 2020/10/20
 */
public class LC438 extends LC76_4 implements TwoProblem {
    public List<Integer> findAnagrams(String s, String p) {
        int[] xx = new int[26];
        HashSet<Integer> xxs = new HashSet<>();
        for (int i = 0; i < p.length(); i++) {
            int c1 = p.charAt(i) - 'a';
            xx[c1]++;
            xxs.add(c1);
        }
        int counter = xxs.size();//总counter, 大valid
        int left = 0, right = 0;
        List<Integer> result = new LinkedList<>();
        while (right < s.length()) {
            int c1 = s.charAt(right) - 'a';
            if (!xxs.contains(c1)) {//不是所需, 从头开始 ??
                while (left < right) {
                    int c2 = s.charAt(left) - 'a';
                    xx[c2]++;//吐出来
                    left++;
                }
                right++;
                left = right;
                counter = xxs.size();
            } else {
                while (xx[c1] == 0) {//如果c1已经够了, left++往出吐
                    int c2 = s.charAt(left) - 'a';
                    xx[c2]++;
                    if (xx[c2] == 1) {
                        counter++;
                    }
                    left++;
                }
                if (xx[c1] > 0) {//是所缺字母, 则counter--
                    xx[c1]--;//放进去
                    if (xx[c1] == 0) {
                        counter--;
                    }
                    if (counter == 0) {//这里和别的区别是不用循环了, 吐出一个就够了
                        result.add(left);
                        int c2 = s.charAt(left) - 'a';
                        xx[c2]++;
                        left++;
                        counter++;//make it invalid
                    }
                    right++;
                } else {
                    throw new RuntimeException();
                }

            }
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(new LC438().findAnagrams("cbaebabacd", "aba"));//5
        System.out.println(new LC438().findAnagrams("cbaebabacd", "abc"));//0,6
        System.out.println(new LC438().findAnagrams("abcabc", "abc"));//0 1 2 3
    }
}
